#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "psm.h"
#include "rINDIE.h"


/*
	Note: I think this method is flawed. What it's doing is this:
		- For each possible antiunitifaction AU
			- select the best refinement and
			- recursively call INDIE2C
		- Then go over all the results, and add the on with the shortest number of rules to the hypothesis

	But, notice that also the internal recursive calls are doing this!!! So, when a node N decides a set of rules,
	the parent node of N cannot remove them, even if N was not selected to be in the final hypothesis.
*/


bool rINDIEHypothesis::learn2c(List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic)
{
	FeatureTerm *solution;
	List<FeatureTerm> solutions;
	List< List<FeatureTerm> > descriptions;
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;


	/* Compute the different solutions: */ 
	{
		int pos;
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;

			if (s!=0) {		
				pos=solutions.Position(s);
				if (pos==-1) {
					solutions.Add(s);
					tmp=new List<FeatureTerm>;
					tmp->Add(d);
					descriptions.Add(tmp);
				} else {
					delete s;
					descriptions[pos]->Add(d);
				} /* if */ 
			} // if
		} /* while */ 
	}

	/* Compute the default solution: */ 
	{
		int max=-1;
		FeatureTerm *s;
		List<FeatureTerm> *tmp;

		m_default_solution=0;

		solutions.Rewind();
		descriptions.Rewind();

		while(solutions.Iterate(s) &&  descriptions.Iterate(tmp)) {
			if (max==-1 || tmp->Length()>max) {
				max=tmp->Length();
				delete m_default_solution;
				m_default_solution=new FeatureTerm(s);
			} /* if */ 
		} /* while */ 
	}

	solutions.Rewind();
	while(solutions.Iterate(solution)) {
		/* Learn a set of patterns for the current solution: */ 
		{
			char *s=solution->toStringNOOS(domain_model);
			printf("\nrINDIE2C: building model for %s --------------------------------------------------\n\n",s);
			delete []s;
		}

		/* Create the positive and negative examples lists: */ 
		{
			FeatureTerm *sol,*des;
			List<FeatureTerm> l1,*tmp;
			List< List<FeatureTerm> > l2;

			l1.Instance(solutions);
			l2.Instance(descriptions);
			while(l1.Iterate(sol) && l2.Iterate(tmp)) {
				if (*sol==*solution) {
					tmp->Rewind();
					while(tmp->Iterate(des)) positive.Add(des);
				} else {
					tmp->Rewind();
					while(tmp->Iterate(des)) negative.Add(des);
				} /* if */ 
			} /* while */ 
		}

		FeatureTerm *description;

		description=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);
		INDIE2C(description,solution,&positive,&negative,heuristic,o,domain_model);
		delete description;

		while(!positive.EmptyP()) positive.ExtractIni();
		while(!negative.EmptyP()) negative.ExtractIni();
	} /* while */ 

	return true;
} /* rINDIEHypothesis::learn2c */ 




bool rINDIEHypothesis::learn2c_single_class(FeatureTerm *solution,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic)
{
	List<FeatureTerm> solutions;
	List< List<FeatureTerm> > descriptions;
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;


	/* Compute the different solutions: */ 
	{
		int pos;
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;
			
			pos=solutions.Position(s);
			if (pos==-1) {
				solutions.Add(s);
				tmp=new List<FeatureTerm>;
				tmp->Add(d);
				descriptions.Add(tmp);
			} else {
				delete s;
				descriptions[pos]->Add(d);
			} /* if */ 
		} /* while */ 
	}

	/* Compute the default solution: */ 
	{
		int max=-1;
		FeatureTerm *s;
		List<FeatureTerm> *tmp;

		m_default_solution=0;

		solutions.Rewind();
		descriptions.Rewind();

		while(solutions.Iterate(s) &&  descriptions.Iterate(tmp)) {
			if (max==-1 || tmp->Length()>max) {
				max=tmp->Length();
				delete m_default_solution;
				m_default_solution=new FeatureTerm(s);
			} /* if */ 
		} /* while */ 
	}

	/* Learn a set of patterns for the current solution: */ 
	{
		char *s=solution->toStringNOOS(domain_model);
		printf("\nrINDIE2C: building model for %s --------------------------------------------------\n\n",s);
		delete []s;
	}

	/* Create the positive and negative examples lists: */ 
	{
		FeatureTerm *sol,*des;
		List<FeatureTerm> l1,*tmp;
		List< List<FeatureTerm> > l2;

		l1.Instance(solutions);
		l2.Instance(descriptions);
		while(l1.Iterate(sol) && l2.Iterate(tmp)) {
			if (*sol==*solution) {
				tmp->Rewind();
				while(tmp->Iterate(des)) positive.Add(des);
			} else {
				tmp->Rewind();
				while(tmp->Iterate(des)) negative.Add(des);
			} /* if */ 
		} /* while */ 
	}

	FeatureTerm *description;

	description=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);
	INDIE2C(description,solution,&positive,&negative,heuristic,o,domain_model);
	delete description;

	while(!positive.EmptyP()) positive.ExtractIni();
	while(!negative.EmptyP()) negative.ExtractIni();

	return true;
} /* rINDIEHypothesis:learn2c_single_class */ 



void rINDIEHypothesis::INDIE2C(FeatureTerm *description,FeatureTerm *solution,List<FeatureTerm> *positive,List<FeatureTerm> *negative,int heuristic,Ontology *o,FTKBase *domain_model)
{
	List<FeatureTerm> initial_l;
	List<FeatureTerm> au_l;
	FeatureTerm *au;
	List<FeatureTerm> negative_covered,negative_uncovered;
	List<FeatureTerm> positive_covered,positive_uncovered;
	List<rINDIEHypothesis> hypothesis_l;
	rINDIEHypothesis *h;

	initial_l.Add(new FeatureTerm(description));

//	printf("rINDIE2C: computing antiunification with %i objects...\n",positive->Length());
	antiunification(&au_l,positive,SPECIALIZATION_LANGUAGE_L2,&initial_l,o,domain_model,true,AU_VERSION_STANDARD);
//	antiunification(&au_l,positive,SPECIALIZATION_LANGUAGE_L1S,&initial_l,o,domain_model,true,AU_VERSION_STANDARD);
//	printf("rINDIE2C: %i posible antiunifications\n",au_l.Length());

	while(!au_l.EmptyP()) {
		List<FeatureTerm> l;
		FeatureTerm *example;

		au=au_l.ExtractIni();
/*
		{
			char *s;
			s=au->toStringNOOS(domain_model);
			printf("%s\n",s);
			delete []s;
		}
*/
		h=new rINDIEHypothesis(this);
		hypothesis_l.Add(h);


		l.Instance(*negative);
		l.Rewind();
		while(l.Iterate(example)) {
			if (au->subsumes(example)) {
				negative_covered.Add(example);
			} else {
				negative_uncovered.Add(example);
			} /* if */ 
		} /* while */ 

		if (negative_covered.EmptyP()) {
			/* Rule found!!! */ 
			{
				FeatureTerm *f;
				f=au;
				au=generalize_pattern(au,positive,negative,o,domain_model);
				delete f;
				h->m_patterns.Add(au);
			}
			h->m_solutions.Add(new FeatureTerm(solution));
			h->m_reliability.Add(new float(1));

			printf("rINDIE2C: new rule found , covers %i positive examples and 0 negative examples\n",positive->Length());
			{
				char *s1,*s2;
				s1=solution->toStringNOOS(domain_model);
				s2=au->toStringNOOS(domain_model);
				printf("rINDIE2C: rule is for class %s,\n%s\n\n",s1,s2);
				delete []s1;
				delete []s2;
			}					
		} else {
			/* Rule is too general, the space of problems has to be partitioned: */ 
			List<FeatureTerm> *refinements;
			FeatureTerm *refinement;
			int selected,nrefinements;
			float *heuristics;
			int i;

			refinements = DSpecializationL2_b(au,positive,0,o,domain_model);
//			refinements = DSpecializationL1S_b(au,positive,0,o,domain_model);

			/* Choose one refinement according to the heuristic: */ 

			/* Filter refinements: */ 
			{
				List<FeatureTerm> to_delete;

				refinements->Rewind();
				while(refinements->Iterate(refinement)) {
					if (refinement->subsumes(au)) to_delete.Add(refinement);
				} /* while */ 

				while(!to_delete.EmptyP()) {
					refinement=to_delete.ExtractIni();
					refinements->DeleteElement(refinement);
					delete refinement;
				} /* while */ 
			}
		
			selected=-1;
			if (refinements->Length()>0) {

				/* Evaluate all the refinements: */ 
				nrefinements=refinements->Length();
				heuristics=new float[nrefinements];
//				printf("Heuristics (for %i refinements):\n",refinements->Length());
				i=0;
				refinements->Rewind();
				while(refinements->Iterate(refinement)) {
/*
					{
						char *s;
						s=refinement->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
					}
*/
					switch(heuristic) {
					case 0:	/* Information Gain: */ 
							{
								int before_p=0,before_n=0,before=0;
								int after_p=0,after_n=0,after=0;
								float before_i,after_i1,after_i2;
								FeatureTerm *f;
								double LOG2E=log(2.0);

								before=positive->Length()+negative->Length();
								positive->Rewind();
								while(positive->Iterate(f)) {
									if (au->subsumes(f)) before_p++;
									if (refinement->subsumes(f)) after_p++;
								} /* if */ 
								negative->Rewind();
								while(negative->Iterate(f)) {
									if (au->subsumes(f)) before_n++;
									if (refinement->subsumes(f)) after_n++;
								} /* if */ 

								after=after_p+after_n;

								before_i=float(-(log(float(before_p)/float(before_p+before_n))/LOG2E));
								if (after==0) {
									after_i1=0;
								} else {
									if (after_p==0) {
										after_i1=1;
									} else {
										after_i1=float(-(log(float(after_p)/float(after))/LOG2E));
									} /* if */ 
								} /* if */ 
								if (before-after==0) after_i2=0;
												   else after_i2=float(-(log(float(before_p-after_p)/float(before-after))/LOG2E));


								heuristics[i]=-(before_i-(after*after_i1+(before-after)*after_i2)/before);
//								printf("%i: %g [%i,%i] -> [%i,%i]/[%i,%i]\n",i,heuristics[i],before_p,before_n,after_p,after_n,before_p-after_p,before_n-after_n);
							}
							break;
					case 1: /* RLDM: */ 
							heuristics[i]=0;
							break;
					default:heuristics[i]=0;
							break;
					} /* switch */ 
						

					i++;
				} /* while */ 

				/* Choose one refinement: */ 
				{
					int i;
					float maximum=heuristics[0];
					selected=0;

					for(i=1;i<nrefinements;i++) {
						if (heuristics[i]>maximum) {
							maximum=heuristics[i];
							selected=i;
						} /* if */ 
					} /* for */  
				}

//				printf("Refinement selected: %i\n",selected);
				refinement=refinements->operator [](selected);

				l.Instance(*positive);
				l.Rewind();
				while(l.Iterate(example)) {
					if (refinement->subsumes(example)) {
						positive_covered.Add(example);
					} else {
						positive_uncovered.Add(example);
					} /* if */ 
				} /* while */ 

				if (!positive_covered.EmptyP()) h->INDIE2C(refinement,solution,&positive_covered,negative,heuristic,o,domain_model);
				if (!positive_uncovered.EmptyP() && positive_uncovered.Length()<positive->Length()) h->INDIE2C(description,solution,&positive_uncovered,negative,heuristic,o,domain_model);

				delete []heuristics;
			} /* if */ 
	
			delete refinements;
			delete au;
		} /* if */ 
		
		while(!negative_covered.EmptyP()) negative_covered.ExtractIni();
		while(!negative_uncovered.EmptyP()) negative_uncovered.ExtractIni();
		while(!positive_covered.EmptyP()) positive_covered.ExtractIni();
		while(!positive_uncovered.EmptyP()) positive_uncovered.ExtractIni();
	} /* while */ 

	/* Select the smallest hypothesis: */ 
	{
		rINDIEHypothesis *selected=0;
		int min_size=-1;

		hypothesis_l.Rewind();
		while(hypothesis_l.Iterate(h)) {
			if (selected==0 || h->m_patterns.Length()<min_size) {
				min_size=h->m_patterns.Length();
				selected=h;
			} /* if */ 
		} /* while */ 

		if (selected!=0) {	
			printf("rINDIE2C: Selected hypothesis with %i rules!\n",min_size);
			m_patterns.Copy(selected->m_patterns);
			m_solutions.Copy(selected->m_solutions);
			m_reliability.Copy(selected->m_reliability);
		} else {
			printf("rINDIE2C: error selecting hypothesis!\n");
		} /* if */ 
	}

	initial_l.Delete();
	au_l.Delete();
	hypothesis_l.Delete();


} /* rINDIEHypothesis::INDIE2C */ 

